package greed;

import java.util.ArrayDeque;
import java.util.Deque;

public class canJump {
    public boolean canJump(int[] nums) {
        if (nums.length==1) {
            return true;
        }
        boolean[] mark = new boolean[nums.length];
        Deque<Integer> queue = new ArrayDeque<>();
        // 存放数组的下标
        queue.offer(0);
        mark[0] = true;
        while (!queue.isEmpty()) {
            Integer index = queue.poll();
            int range = nums[index];
            // 入队列的时候就要mark，且判断是否越界
            for (int i = 1; i <= range; i++) {
                int pos = index + i;
                if (pos >= nums.length - 1) {
                    return true;
                } else {
                    if (!mark[pos]) {
                        queue.offer(pos);
                        mark[pos] = true;
                    }

                }
            }

        }

        return false;
    }

    public static void main(String[] args) {
        canJump obj = new canJump();
        // int[] nums = new int[]{2,3,1,1,4};
        int[] nums = new int[]{3,2,1,0,4};
        System.out.println(obj.canJump(nums));
    }
}
